#include <map>
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

class Solution
{
public:
    void calc(vector<string> &res, string str, string &digits, map<char, string> &hashmap, int k)
    {
        if (str.size() == digits.size())
        {
            res.push_back(str);
            return;
        }
        string tmp = hashmap[digits[k]];
        for (char c : tmp)
        {
            str += c;
            calc(res, str, digits, hashmap, k + 1);
            str.pop_back();
        }
        return;
    }
    vector<string> letterCombinations(string digits)
    {
        map<char, string> table{
            {'0', " "}, {'1', "*"}, {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
        vector<string> res;
        if (digits == "")
            return res;
        calc(res, "", digits, table, 0);
        return res;
    }
};